The present invention concerns the placement of components so as to regularize the location of data paths in very large scale integrated (VLSI) circuits.
In the design of integrated circuits, circuitry consists of functional blocks of logic, often called components, which are interconnected by connection lines. In data path circuits, these connection lines include connection lines on which are placed data signals, called data signal connection networks, and connection lines on which are placed control signals, called control signal connection networks.
One approach for laying out the circuitry of complex VLSI circuits is the use of a hierarchical layout design. In such an approach the components are first partitioned into clusters. For an example of a prior method for partitioning components into clusters see, for example, C. M. Fiduccia and R. M. Mattheyses, A Linear-Time Heuristic for Improving Network Partitions, Proceedings of the 19th Design Automation Conference, 1982, pp. 241-247.
Once partitioned, a global placement algorithm is used to place the clusters in locations on the circuit. After placement of clusters, detail placement algorithms are used to place individual components within each cluster. After an initial placement of clusters and components, placement improvement algorithms may be used to optimize the placement of components within the clusters. Once the clusters and components have been placed, connection line routers are used to route connection line networks between the components. For examples of other placement techniques, see generally, Maurice Hanan, Peter K. Wolff, Sr. and Barbara J. Agule, Some Experimental Results of Placement Techniques, Proceedings of the 13th Design Automation Conference, 1976, pp. 214-224; Carl Sechen and Alberto Sangiovanni-Vincentelli, The TimberWolf Placement and Routing Package, IEEE Journal of Solid-State Circuits, 1985, pp. 510-522.
One scheme in the prior art describes an automatic partitioning and placement system which makes use of circuit structure and hierarchical design data in addition to the connectivity between circuit elements. See Gotaro Odawara, Takahisa Hiraide, and Osamu Nishina, Partitioning and Placement Technique for CMOS Gate Arrays, IEEE Transactions on Computer-aided Design, 1987, pp. 355-363. In this scheme, regular structures are extracted from a netlist and then treated as clusters in a placement algorithm. This method, however, requires a completely new placement scheme to handle the regular structures in the netlist. Further, the method is optimized for a hierarchical and structural netlist.